package leetcode;

public class Code35 {
    public static void main(String[] args) {
        System.out.println(new Code35().searchInsert(new int[]{1, 3, 5, 6}, 4));
    }

    public int searchInsert(int[] nums, int target) {
        return find(nums, 0, nums.length - 1, target,true);
    }

    public int find(int[] nums, int start, int end, int taget,boolean left) {
        if (start > end) {
            return left?start:end+1;
        }
        int index = nums[(start + end) / 2];
        if (index > taget) {
            return find(nums, start, (start + end) / 2 - 1, taget,true);
        } else if (index < taget) {
            return find(nums, (start + end) / 2 + 1, end, taget,false);
        } else {
            return (start + end) / 2;
        }
    }
}
